# 最小生成树相关算法

snippet prim "Description" b
TODO
endsnippet

snippet kruskal "kruskal算法" b
//============== kruskal算法
// 传入点数，返回mst的值，不连通返回-1
namespace Kruskal {
    using namespace xlx1;
    bool cmp( _e a,_e b) {return a.w < b.w;}
    int work(int n){
        BCJ::bcj_init(n); //初始化
        sort(e+1,e+1+edge_cnt,cmp); //对边从小到大排序
        int ans = 0,cnt = 0; //答案，选边的数量
        n++; //多了个超级点 0

        for(int i = 1; i<=edge_cnt ; ++i){
            int u =e[i].u, v =e[i].v, w =e[i].w; 
            int f1 =BCJ::find(u),f2 = BCJ::find(v);
            if( f1 != f2){ //不再同一个集合
                //printf("%d %d %d\n",u,v,w);
                ans+=w;
                cnt++;
                BCJ::fa[f2] = f1;
            }
            if( cnt == n-1) break;
        }
        if( cnt < n -1) return -1;
        return ans;
    }
}
//============== kruskal算法 END
$0
endsnippet

# 次小生成树
snippet sec_mst "次小生成树" b
namespace SEC_MST {
}
endsnippet
